/* 增加一个指向双亲节点的 parent 指针，输出所有节点到根节点的路径 */

#include <iostream>
#include "ParentTreefun.h"
using namespace std;

// 打印当前结点到根结点的路径
void printpath(BTNode *p)
{
  while (p != NULL)
  {
    cout << p->data << " ";
    p = p->parent;
  }
}

// 打印所有结点到根结点的路径
void allpath(BTNode *p)
{
  // 当前结点不为空
  if (p != NULL)
  {
    cout << "到根结点的路径为:";
    
    // 打印当前结点到根结点的路径
    printpath(p);
    
    // 打印左子树的所有结点到根结点的路径
    allpath(p->lchild);
    
    // 打印右子树的所有结点到根结点的路径
    allpath(p->rchild);
  }
}

int main()
{
  // 创建含双亲指针的二叉树
  BTNode *T, *p = NULL;
  create_parent_tree(T, p);
  
  // 打印所有结点到根结点的路径
  allpath(T);
}
